#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

#define MAX_SIZE 65536

static bool LOG = false;

void Gen(const int& n, int* out, bool* is_white) {
  for (int i = 0; i < n; ++i) {
    out[i] = i + 1;
    is_white[i] = (rand() & 1);
  }
  for (int i = n - 1; i > 0; --i) {
    int j = rand() % (i + 1);
    int tmp = out[i];
    out[i] = out[j];
    out[j] = tmp;
  }
}

void BruteForce(const int* input, const bool* is_white, const int& n, int* ans) {
  for (int i = 0; i < n; ++i) {
    ans[i] = -1;
    if (is_white[i]) {
      for (int j = 0; j < i; ++j) {
        if (!is_white[j] && input[j] < input[i] && input[j] > ans[i])
          ans[i] = input[j];
      }
    }
  }
}

void Display(const int* array, const int& n) {
  for (int i = 0; i < n; ++i) {
    printf("%2d ", array[i]);
  }
  printf("\n");
}

#define DISPLAY(array, size) {\
  printf("%15s: ", #array);\
  Display(array, size);\
}

#define DISPLAY_BOOL(array, size) {\
  printf("%15s: ", #array);\
  for (int idx = 0; idx < n; ++idx) {\
    if (array[idx]) printf(" * ");\
    else printf("   ");\
  }\
  printf("\n");\
}

void FastWithUnionSet(const int* input, const bool* is_white, const int& n, int* ans) {
  int fa[n];
  bool inv_is_white[n];
  for (int i = 0; i < n; ++i) {
    inv_is_white[input[i] - 1] = is_white[i];
    fa[i] = i - 1;
    ans[i] = -1;
  }
  if (LOG) {
    DISPLAY_BOOL(inv_is_white, n);
    DISPLAY(fa, n);
    printf("\n");
  }

  for (int i = n - 1; i >= 0; --i) {
    int num = input[i] - 1;
    if (inv_is_white[num]) {
      int f = num;
      while (fa[f] != -1 && inv_is_white[fa[f]]) {
        f = fa[f];
      }
      for (int j = num; j != f;) {
        int k = fa[j];
        fa[j] = f;
        j = k;
      }
      if (fa[f] != -1) ans[i] = fa[f] + 1;
    } else {
      inv_is_white[num] = true;
    }

    if (LOG) {
      DISPLAY(fa, n);
      printf("\n");
    }
  }
}

bool CheckResult(const int* input, const bool* is_white, const int* to_check, const int* correct, const int& n) {
  for (int i = 0; i < n; ++i) {
    if (to_check[i] != correct[i]) {
      printf("Wrong answer: \n");
      DISPLAY(input, n);
      DISPLAY_BOOL(is_white, n);
      DISPLAY(correct, n);
      DISPLAY(to_check, n);
      return false;
    }
  }
  return true;
}

int input[MAX_SIZE];
int ans[MAX_SIZE];
int to_check[MAX_SIZE];
bool is_white[MAX_SIZE];

int main() {
  srand(time(0));
  const int kSize[] = {5, 6, 7, 8, 9, 10, 15, 20, 30, 40, 50, 100, 1000, 10000};
  const int kNumCases = sizeof(kSize) / sizeof(int);

  for (int i = 0; i < kNumCases; ++i) {
    int n = kSize[i];
    bool succeed = true;
    printf("Testing case %d (n=%d):\n", i + 1, n);

    for (int j = 0; j < 100; ++j) {
      Gen(n, input, is_white);
      BruteForce(input, is_white, n, ans);
      FastWithUnionSet(input, is_white, n, to_check);
      succeed = CheckResult(input, is_white, to_check, ans, n);
      if (!succeed) break;
    }
    if (!succeed) break;
    printf("\n");
  }
  return 0;
}
